import javafx.scene.control.TableRow;

import java.util.*;

public class ReconstructItinerary {
    /*
    * 332. 重新安排行程
    * 给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。
    * 请你对该行程进行重新规划排序。
    * 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，
    * 所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
    * 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
    * 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
    *
    * 1 <= tickets.length <= 300
    * tickets[i].length == 2
    * fromi.length == 3
    * toi.length == 3
    * fromi 和 toi 由大写英文字母组成
    * fromi != toi
    * */
    public static void main(String[] args){

    }

    // 我的想法：按照到达地排个序，然后回溯，用set记录已经用过的票
    // 过是能过，但确实是太慢了，30-40ms
    public List<String> mySolution(List<List<String>> tickets){
        Collections.sort(tickets, Comparator.comparing(a -> a.get(1)));
        path.add("JFK");
        used = new int[tickets.size()];
        backTracking(tickets);
        return path;
    }
    LinkedList<String> path = new LinkedList<>();
    int[] used;
    private boolean backTracking(List<List<String>> tickets){
        if(path.size() == tickets.size() + 1)
            return true;

        for (int i = 0; i < tickets.size(); i++) {
            if(!path.peekLast().equals(tickets.get(i).get(0)) || used[i] == 1)
                continue;
            path.add(tickets.get(i).get(1));
            used[i] = 1;
            if(backTracking(tickets))
                return true;
            path.pollLast();
            used[i] = 0;

        }
        return false;
    }

    // 用map<String, Map<String, Integer>>来记录一个地点到另外地点的关系映射以及边数
    // 快了不少
    HashMap<String, Map<String, Integer>> map = new HashMap<>();
    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> t : tickets){
            Map<String, Integer> temp;
            if(map.containsKey(t.get(0))){
                temp = map.get(t.get(0));
                temp.put(t.get(1), temp.getOrDefault(t.get(1), 0)+1);
            } else {
                temp = new TreeMap<>();
                temp.put(t.get(1), 1);
            }
            map.put(t.get(0), temp);
        }
        path.add("JFK");
        backtracking(tickets);
        return path;
    }

    private boolean backtracking(List<List<String>> tickets){
        if(path.size() == tickets.size()+1)
            return true;

        String last = path.peekLast();
        if(map.containsKey(last)) {
            for (Map.Entry<String, Integer> entry : map.get(last).entrySet()) {
                int count = entry.getValue();
                if (count > 0) {
                    path.add(entry.getKey());
                    entry.setValue(count - 1);
                    if (backtracking(tickets)) return true;
                    path.pollLast();
                    entry.setValue(count);
                }
            }
        }
        return false;
    }

}
// 官方题解
// 快，而且简洁，而且看着清晰
class Solution {
    Map<String, PriorityQueue<String>> map = new HashMap<String, PriorityQueue<String>>();
    List<String> itinerary = new LinkedList<String>();

    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> ticket : tickets) {
            String src = ticket.get(0), dst = ticket.get(1);
            if (!map.containsKey(src)) {
                map.put(src, new PriorityQueue<String>());
            }
            map.get(src).offer(dst);
        }
        dfs("JFK");
        Collections.reverse(itinerary);
        return itinerary;
    }

    public void dfs(String curr) {
        while (map.containsKey(curr) && map.get(curr).size() > 0) {
            String tmp = map.get(curr).poll();
            dfs(tmp);
        }
        itinerary.add(curr);
    }
}